package com.example.arithmeticleetcode.leetcode.jan;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2021-01-20 18:01
 **/
public class Demo16 {

    public static void main(String[] args) {

    }

    public boolean isEvenOddTree(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;
        while (!queue.isEmpty()) {
            //偶数行  奇数元素 递增     奇数行   偶数元素 递减
            boolean flag = (level & 1) == 0;
            TreeNode pre = queue.poll();
            int len = queue.size();
            if (flag) {
                //偶数是偶数
                if ((pre.val & 1) == 0) return false;
            } else {
                //奇数是奇数
                if ((pre.val & 1) == 1) return false;
            }
            if (pre.left != null) {
                queue.add(pre.left);
            }
            if (pre.right != null) {
                queue.add(pre.right);
            }
            for (int i = 1; i < len; i++) {
                TreeNode num = queue.poll();
                //偶数
                if (flag) {
                    if ((pre.val & 1) == 0 || pre.val > num.val) return false;
                } else {
                    if ((pre.val & 1) == 1 || pre.val < num.val) return false;
                }
                pre = num;
                if (num.left != null) {
                    queue.add(num.left);
                }
                if (num.right != null) {
                    queue.add(num.right);
                }
            }
            level++;
        }
        return true;
    }


}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}